/*
 * @lc app=leetcode.cn id=108 lang=java
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * Accepted
    31/31 cases passed (0 ms)
    Your runtime beats 100 % of java submissions
    Your memory usage beats 85.88 % of java submissions (41.1 MB)
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l == r)
            return new TreeNode(nums[l]);
        if (r > l) {
            int mid = (r + l + 1) / 2;
            return new TreeNode(nums[mid], buildTree(nums, l, mid - 1), buildTree(nums, mid + 1, r));
        }
        return null;
    }
}
// @lc code=end
